{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Asteroid Collision"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: asteroidCollision"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #小行星碰撞"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组 <code>asteroids</code>，表示在同一行的小行星。</p>\n",
    "\n",
    "<p>对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。</p>\n",
    "\n",
    "<p>找出碰撞后剩下的所有小行星。碰撞规则：两个小行星相互碰撞，较小的小行星会爆炸。如果两颗小行星大小相同，则两颗小行星都会爆炸。两颗移动方向相同的小行星，永远不会发生碰撞。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>asteroids = [5,10,-5]\n",
    "<strong>输出：</strong>[5,10]\n",
    "<b>解释：</b>10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>asteroids = [8,-8]\n",
    "<strong>输出：</strong>[]\n",
    "<b>解释：</b>8 和 -8 碰撞后，两者都发生爆炸。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>asteroids = [10,2,-5]\n",
    "<strong>输出：</strong>[10]\n",
    "<b>解释：</b>2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= asteroids.length&nbsp;&lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-1000 &lt;= asteroids[i] &lt;= 1000</code></li>\n",
    "\t<li><code>asteroids[i] != 0</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [asteroid-collision](https://leetcode.cn/problems/asteroid-collision/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [asteroid-collision](https://leetcode.cn/problems/asteroid-collision/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,10,-5]', '[8,-8]', '[10,2,-5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack = [\"#\"]\n",
    "        i = 0\n",
    "        while i<len(asteroids):\n",
    "            asteroid = asteroids[i]\n",
    "            top_elem = stack[-1]\n",
    "            if stack[-1] == \"#\":\n",
    "                stack.append(asteroid)\n",
    "                i += 1\n",
    "            elif stack[-1]>0:\n",
    "                if asteroid >0:\n",
    "                    stack.append(asteroid)\n",
    "                    i += 1\n",
    "                else:\n",
    "                    s = stack[-1]+asteroid\n",
    "                    if s == 0:\n",
    "                        stack.pop()\n",
    "                        i += 1\n",
    "                    elif s<0:\n",
    "                        stack.pop()\n",
    "                    else:\n",
    "                        i += 1\n",
    "            else:\n",
    "                stack.append(asteroid)\n",
    "                i += 1\n",
    "\n",
    "        return stack[1:]\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids):\n",
    "        \"\"\"\n",
    "        :type asteroids: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        i = 0\n",
    "        while(i < len(asteroids)-1 and len(asteroids) != 0):\n",
    "            if asteroids[i] > 0 and asteroids[i+1] > 0:\n",
    "                i += 1\n",
    "            elif asteroids[i] < 0 and asteroids[i+1] < 0:\n",
    "                i += 1\n",
    "            elif asteroids[i] < 0 and asteroids[i+1] > 0:\n",
    "                i += 1\n",
    "            else:\n",
    "                if abs(asteroids[i]) > abs(asteroids[i+1]):\n",
    "                    asteroids.pop(i+1)\n",
    "                elif abs(asteroids[i]) < abs(asteroids[i+1]):\n",
    "                    asteroids.pop(i)\n",
    "                    if i != 0:\n",
    "                        i -= 1\n",
    "                else:\n",
    "                    asteroids.pop(i)\n",
    "                    asteroids.pop(i)\n",
    "                    if i != 0:\n",
    "                        i -= 1\n",
    "            \n",
    "        return asteroids\n",
    "                    \n",
    "                    \n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: 'List[int]') -> 'List[int]':\n",
    "        #  终于自己写出来一道栈的题目还不那么差效率了- -再一道睡觉，不要再一道就天亮了...\n",
    "        s = []\n",
    "        x = False\n",
    "        for i in range(len(asteroids)):\n",
    "            if not s:\n",
    "                s.append(asteroids[i])\n",
    "            else:\n",
    "                if asteroids[i] > 0:\n",
    "                    s.append(asteroids[i])\n",
    "                else:\n",
    "                    if s[-1] > 0:\n",
    "                        if s[-1] < abs(asteroids[i]):\n",
    "                            while s and s[-1] > 0 and s[-1] <= abs(asteroids[i]):\n",
    "                                if s[-1] < abs(asteroids[i]):\n",
    "                                    s.pop()\n",
    "                                elif s[-1] == abs(asteroids[i]):\n",
    "                                    s.pop()\n",
    "                                    x = True\n",
    "                                    break\n",
    "                            if not x:\n",
    "                                if not s or s[-1] < 0:\n",
    "                                    s.append(asteroids[i])\n",
    "                            else:\n",
    "                                x = False\n",
    "                        elif s[-1] == abs(asteroids[i]):\n",
    "                            s.pop()\n",
    "                    else:\n",
    "                        s.append(asteroids[i])\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids):\n",
    "        \"\"\"\n",
    "        :type asteroids: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        ans, n, i, stack = [], len(asteroids), 0, []\n",
    "        while i < n:\n",
    "            if asteroids[i] < 0:\n",
    "                while stack and stack[-1] < -asteroids[i]:\n",
    "                    stack.pop()\n",
    "                if not stack:\n",
    "                    ans.append(asteroids[i])\n",
    "                elif stack[-1] == -asteroids[i]:\n",
    "                    stack.pop()\n",
    "            else:\n",
    "                stack.append(asteroids[i])\n",
    "            i += 1\n",
    "        ans.extend(stack)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids):\n",
    "        \"\"\"\n",
    "        :type asteroids: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        negatives = []\n",
    "        positives = []\n",
    "        for asteroid in asteroids:\n",
    "            if asteroid > 0:\n",
    "                positives.append(asteroid)\n",
    "            else:\n",
    "                shouldAddNegative = True\n",
    "                while positives:\n",
    "                    sum = positives[-1] + asteroid\n",
    "                    if sum == 0:\n",
    "                        positives.pop()\n",
    "                        shouldAddNegative = False\n",
    "                        break\n",
    "                    elif sum > 0:\n",
    "                        shouldAddNegative = False\n",
    "                        break\n",
    "                    else:\n",
    "                        positives.pop()\n",
    "                if shouldAddNegative:\n",
    "                    negatives.append(asteroid)\n",
    "                \n",
    "        return negatives + positives"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids):\n",
    "        \"\"\"\n",
    "        :type asteroids: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        l = len(asteroids)\n",
    "        if l<2:\n",
    "            return asteroids\n",
    "        i=0\n",
    "        while(i<l):\n",
    "            if len(res)==0:\n",
    "                res.append(asteroids[i])\n",
    "                i+=1\n",
    "            else:\n",
    "                top = res[-1]\n",
    "                cur = asteroids[i]\n",
    "                if top>0 and cur<0:\n",
    "                    a = abs(cur)\n",
    "                    if top == a:\n",
    "                        res.pop()\n",
    "                        i+=1\n",
    "                    elif top<a:\n",
    "                        res.pop()\n",
    "                    elif top>a:\n",
    "                        i+=1\n",
    "                else:\n",
    "                    res.append(cur)\n",
    "                    i+=1\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        n=len(asteroids)\n",
    "        on,off=0,1\n",
    "        if n==1:\n",
    "            return asteroids\n",
    "        while on<off and off<n:\n",
    "            if asteroids[on]>0 and asteroids[off]<0:\n",
    "                if asteroids[on]>abs(asteroids[off]):\n",
    "                    asteroids.pop(off)\n",
    "                    n-=1\n",
    "                elif asteroids[on]<abs(asteroids[off]):\n",
    "                    asteroids.pop(on)\n",
    "                    on-=1\n",
    "                    off-=1\n",
    "                    n-=1\n",
    "                else:\n",
    "                    asteroids.pop(on)\n",
    "                    asteroids.pop(on)\n",
    "                    on-=1\n",
    "                    off-=1\n",
    "                    n-=2\n",
    "                if on<0:\n",
    "                    on,off=0,1\n",
    "            else:\n",
    "                on+=1\n",
    "                off+=1\n",
    "        return asteroids"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        rst=[0]\n",
    "        while asteroids!=[]:\n",
    "            atop=asteroids[0]\n",
    "            rend=rst[-1]\n",
    "            if atop<0 and rend>0: \n",
    "                    if abs(atop)==abs(rend):\n",
    "                        asteroids.remove(atop)\n",
    "                        rst.pop()\n",
    "                    elif abs(atop)<abs(rend):\n",
    "                        asteroids.remove(atop)\n",
    "                    elif abs(atop)>abs(rend):\n",
    "                        rst.pop()\n",
    "            else :rst.append(asteroids.pop(0))\n",
    "        rst.remove(0)\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        rst=[0]\n",
    "        while asteroids!=[]:\n",
    "            if asteroids[0]<0 and rst[-1]>0: \n",
    "                    if -asteroids[0]==rst[-1]:\n",
    "                        asteroids.pop(0)\n",
    "                        rst.pop()\n",
    "                    elif -asteroids[0]<rst[-1]:\n",
    "                        asteroids.pop(0)\n",
    "                    elif -asteroids[0]>rst[-1]:\n",
    "                        rst.pop()\n",
    "            else :rst.append(asteroids.pop(0))\n",
    "        rst.remove(0)\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        list1 = asteroids\n",
    "        index = 0\n",
    "        while index < len(list1) - 1:\n",
    "            num1 = list1[index]\n",
    "            num2 = list1[index + 1]\n",
    "            if num1 > 0 and num2 < 0:\n",
    "                if abs(num1) < abs(num2):\n",
    "                    del list1[index]\n",
    "                elif abs(num1) > abs(num2):\n",
    "                    del list1[index + 1]\n",
    "                else:\n",
    "                    del list1[index]\n",
    "                    del list1[index]\n",
    "                index = 0\n",
    "            else:\n",
    "                index += 1\n",
    "        return(list1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        while True:\n",
    "            for i in range(1, len(asteroids)):\n",
    "                if asteroids[i-1] > 0 and asteroids[i] < 0:\n",
    "                    s = asteroids[i-1] + asteroids[i]\n",
    "                    if s > 0:\n",
    "                        del asteroids[i]\n",
    "                    elif s < 0:\n",
    "                        del asteroids[i-1]\n",
    "                    else:\n",
    "                        del asteroids[i-1:i+1]\n",
    "                    break\n",
    "            else:\n",
    "                return asteroids"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        if not asteroids:return []\n",
    "        if len(asteroids)==1: return asteroids\n",
    "        save=[]\n",
    "        for i in range(len(asteroids)):\n",
    "            while save:\n",
    "                if save[-1]*asteroids[i]>=0 or save[-1]<0:\n",
    "                    break\n",
    "                if abs(save[-1])>abs(asteroids[i]):\n",
    "                    asteroids[i]=0\n",
    "                elif abs(save[-1])==abs(asteroids[i]):\n",
    "                    save.pop()\n",
    "                    asteroids[i]=0\n",
    "                elif abs(save[-1])<abs(asteroids[i]):\n",
    "                    save.pop()\n",
    "            if asteroids[i]:\n",
    "                save.append(asteroids[i])\n",
    "        return save\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        #思路：从左向右遍历放进堆栈中，若遇到负数，则弹出，并且比较大小，若正数一直较小，则一直弹出，否则\n",
    "        stack = []\n",
    "        for num in asteroids:\n",
    "            if num > 0:\n",
    "                ## 如果是正数的话，直接进入\n",
    "                stack.append(num)\n",
    "            else:\n",
    "                ## 对于负数而言，如果队列为空或者最后一个元素为负数也是直接进\n",
    "                if len(stack) == 0 or stack[-1] < 0:\n",
    "                    stack.append(num)\n",
    "                else:\n",
    "                    ## 表示堆栈里面最后一个是正数\n",
    "                    while stack and stack[-1] > 0:\n",
    "                        if stack[-1] < abs(num):\n",
    "                            stack.pop()\n",
    "                            flag = True\n",
    "                        elif stack[-1] == abs(num):\n",
    "                            #表示num已经毁灭\n",
    "                            stack.pop()\n",
    "                            flag = False\n",
    "                            break\n",
    "                        else:\n",
    "                            flag = False\n",
    "                            break\n",
    "                    ## 判断该点是否进去\n",
    "                    if flag:\n",
    "                        stack.append(num)\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        ll = []\n",
    "        k = -1\n",
    "        for i in range(len(asteroids)):\n",
    "            f=0\n",
    "            if k == -1:\n",
    "                ll.append(asteroids[i])\n",
    "                k = 0\n",
    "            else:\n",
    "                if asteroids[i]>0:\n",
    "                    ll.append(asteroids[i])\n",
    "                    k = k+1\n",
    "                else:\n",
    "                    if ll[k]<0:\n",
    "                        ll.append(asteroids[i])\n",
    "                        k = k+1\n",
    "                    else:\n",
    "                        while(ll[k]>=0 and asteroids[i]+ll[k]<0):\n",
    "                            del ll[k]\n",
    "                            k = k-1 \n",
    "                            if k<0:\n",
    "                                ll.append(asteroids[i])\n",
    "                                k = 0\n",
    "                                f = 1\n",
    "                                break\n",
    "                        if ll[k]<0 and f==0:\n",
    "                            ll.append(asteroids[i])\n",
    "                            k = k+1\n",
    "                        if asteroids[i]+ll[k] == 0:\n",
    "                            del ll[k]\n",
    "                            k = k-1\n",
    "        return ll"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        for new in asteroids:\n",
    "            while ans and new < 0 < ans[-1]:\n",
    "                if ans[-1]<-new:\n",
    "                    ans.pop()\n",
    "                    continue\n",
    "                elif ans[-1] == -new:\n",
    "                    ans.pop()\n",
    "                break\n",
    "            else:\n",
    "                ans.append(new)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        if len(asteroids)<2:\n",
    "            return asteroids\n",
    "        while True:\n",
    "            i=0\n",
    "            flag=0\n",
    "            for j in range (1,len(asteroids)):\n",
    "                #print (i,j)\n",
    "                #print (asteroids)\n",
    "                if asteroids[i]>0 and asteroids[j]<0 :\n",
    "                    flag=1\n",
    "                    if asteroids[i]+asteroids[j] >0:\n",
    "                        asteroids.pop(j)\n",
    "                    elif asteroids[i]+asteroids[j] <0:\n",
    "                        asteroids.pop(i)\n",
    "                    else:\n",
    "                        asteroids.pop(i)\n",
    "                        #print (asteroids)\n",
    "                        asteroids.pop(i)\n",
    "                        #print (asteroids)\n",
    "                    break\n",
    "                i+=1\n",
    "                j+=1\n",
    "            if flag==0:\n",
    "                break \n",
    "        return asteroids\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        for s, t in enumerate(asteroids):\n",
    "            if t<0:\n",
    "                for i in range(s-1,-1,-1):\n",
    "                    if asteroids[i]<0:\n",
    "                        break\n",
    "                    if asteroids[i]>abs(t):\n",
    "                        asteroids[s] = 0\n",
    "                        break\n",
    "                    if asteroids[i]<abs(t):\n",
    "                        asteroids[i] = 0\n",
    "                    if asteroids[i]==abs(t):\n",
    "                        asteroids[i] = 0\n",
    "                        asteroids[s] = 0\n",
    "                        break\n",
    "        return [s for s in asteroids if s !=0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        collide = True\n",
    "        while collide:\n",
    "            collide = False\n",
    "            i = len(asteroids) - 1\n",
    "            while i >= 1:\n",
    "                if asteroids[i] > 0:\n",
    "                    i -= 1\n",
    "                    continue\n",
    "                if asteroids[i - 1] < 0: \n",
    "                    i -= 1\n",
    "                    continue\n",
    "                collide = True\n",
    "                m1 = asteroids[i - 1]\n",
    "                m2 = -asteroids[i]\n",
    "                if m1 < m2:\n",
    "                    asteroids.pop(i - 1)\n",
    "                elif m1 > m2:\n",
    "                    asteroids.pop(i)\n",
    "                else:\n",
    "                    asteroids.pop(i)\n",
    "                    asteroids.pop(i - 1)\n",
    "                    i -= 1\n",
    "                i -= 1\n",
    "        return asteroids\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        rs = [asteroids.pop()]\n",
    "        while asteroids:\n",
    "            cur_asteroid = asteroids.pop()\n",
    "            for i in range(len(rs)):\n",
    "                asteroid = rs[0]\n",
    "                # 左边向右，右边向左，碰撞\n",
    "                if cur_asteroid>0 and asteroid<0:\n",
    "                    if abs(asteroid)>abs(cur_asteroid):  # 当前右边的大，结束\n",
    "                        break\n",
    "                    elif abs(asteroid)==abs(cur_asteroid):  # 相等，消消乐，结束\n",
    "                        rs.pop(0)\n",
    "                        break\n",
    "                    else:\n",
    "                        rs.pop(0)\n",
    "                else:  # 同向或者反向，插入碰撞后(如果有碰撞)留下的星球，结束\n",
    "                    rs.insert(0, cur_asteroid)\n",
    "                    break\n",
    "            else:\n",
    "                rs.insert(0, cur_asteroid)\n",
    "        return rs\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, a: List[int]) -> List[int]:\n",
    "        i = 0\n",
    "        while i < len(a)-1:\n",
    "            if a[i] > 0 and a[i+1] < 0:\n",
    "                if a[i] > -a[i+1]:\n",
    "                    del a[i+1]\n",
    "                elif a[i] < -a[i+1]:\n",
    "                    del a[i]\n",
    "                    if i > 0:\n",
    "                        i -= 1\n",
    "                else:\n",
    "                    del a[i]\n",
    "                    del a[i]\n",
    "                    if i > 0:\n",
    "                        i -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        n=len(asteroids)\n",
    "        stack=[]\n",
    "        for i in asteroids:\n",
    "            bao=True\n",
    "            while i<0 and stack and stack[-1]>0 and bao:\n",
    "                if abs(i)<=stack[-1]:\n",
    "                    bao=False\n",
    "                if abs(i)>=stack[-1]:\n",
    "                    stack.pop()\n",
    "\n",
    "\n",
    "\n",
    "            if bao:\n",
    "                stack.append(i)\n",
    "        return stack   \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        sk=[]\n",
    "        for ast in asteroids:\n",
    "            ok=True\n",
    "            while ok and sk and sk[-1]>0 and ast<0:\n",
    "                a,b=sk[-1],-ast\n",
    "                if a>=b:\n",
    "                    ok=False\n",
    "                if a<=b:\n",
    "                    sk.pop(-1)\n",
    "            if ok:\n",
    "                sk.append(ast)\n",
    "        return sk\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        idx = 0\n",
    "        while (idx < len(asteroids)):\n",
    "            if (idx == 0):\n",
    "                idx += 1\n",
    "            elif asteroids[idx-1] > 0 and asteroids[idx] < 0:\n",
    "                if (abs(asteroids[idx-1]) < abs(asteroids[idx])):\n",
    "                    asteroids.pop(idx-1)\n",
    "                    idx -= 1\n",
    "                elif (abs(asteroids[idx-1]) > abs(asteroids[idx])):\n",
    "                    asteroids.pop(idx)\n",
    "                else:\n",
    "                    asteroids.pop(idx-1)\n",
    "                    asteroids.pop(idx-1)\n",
    "                    idx -= 1\n",
    "            else:\n",
    "                idx += 1\n",
    "        return asteroids\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        for star in asteroids:\n",
    "            alive = True\n",
    "            while alive and stack and stack[-1]>0 and star<0:\n",
    "                alive = stack[-1] < -star\n",
    "                if stack[-1]<=-star:\n",
    "                    stack.pop()\n",
    "            if alive:\n",
    "                stack.append(star)\n",
    "        return stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        for star in asteroids:\n",
    "            while True:\n",
    "                if not stack:\n",
    "                    stack.append(star)\n",
    "                    break\n",
    "                elif stack[-1]>0 and star<0:\n",
    "                    if stack[-1] == -star:\n",
    "                        stack.pop()\n",
    "                        break\n",
    "                    elif stack[-1] < -star:\n",
    "                        stack.pop()\n",
    "                    else:\n",
    "                        break\n",
    "                else:\n",
    "                    stack.append(star)\n",
    "                    break\n",
    "        return stack\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def asteroidCollision(self, asteroids: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "\n",
    "        for i, c in enumerate(asteroids):\n",
    "            if c > 0:\n",
    "                stack.append(c)\n",
    "            else:\n",
    "                # 现在拿到的数字小于0，会发生碰撞\n",
    "                if not stack or stack[-1] < 0:\n",
    "                    stack.append(c)\n",
    "                else:\n",
    "                    while stack and stack[-1] > 0:\n",
    "                        if abs(c) < stack[-1]:\n",
    "                            break\n",
    "                        elif abs(c) > stack[-1]:\n",
    "                            stack.pop()\n",
    "                        else:\n",
    "                            stack.pop()\n",
    "                            break\n",
    "                    else:\n",
    "                        stack.append(c)\n",
    "        return stack"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
